package findBinTreeNextNode;

/**
 * 3.在中序里面，有一下几个特性
 * 1） 如果一个节点有右子树，则此节点的中序中的下个元素一个它右子树的最左结点，例如 B 有右子树，则它的下一个节点是 H
 * 2） 如果一个节点没有右子树，并且它是它父亲节点的左子树。那它的下一个节点是它的父亲节点。
 * 3） 如果一个节点没有右子树，并且它是它父亲节点的右子树。那它的下一个节点有点复杂，需要一直往上找，找到一个父亲节点是左子树，这个节点的父亲节点它的下个节点。
 *
 * */

public class Solution {
    public TreeNode findNext(TreeNode node ){
        TreeNode rs = null ;
        // 先来处理第一种情况，当前节点有右孩子
        if(null != node.getRight()){
           rs = findLeftest(node.getRight());
        }else{
            // 当前节点是左儿子节点
            if(node.getFather() == null){
                // 如果当前节点没有父亲节点，说明它是跟节点，在没有右孩子的情况下，当前节点就是最后一个节点。
                rs = null ;
            }
            if(node.getFather() != null && node.equals(node.getFather().getLeft()) ){
                rs = node.getFather();
            }
            // 当前节点是右儿子节点
            if(node.getFather() != null && node.equals(node.getFather().getRight())){
                rs = findLeftFather(node);
            }
        }
        return rs ;

    }

    private TreeNode findLeftFather(TreeNode node) {
        TreeNode rs = null ;
        TreeNode next = node ;
        while(next != null ){
            if(next.equals(next.getFather().getLeft() )){
               rs = next ;
               break;
            }
            next = next.getFather();
        }
        return rs.getFather() ;
    }

    private TreeNode findLeftest(TreeNode right) {
        TreeNode next = right ;
        TreeNode rs = null ;

        while(next != null){
            rs = next ;
            next = next.getLeft();
        }

        return rs;
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(2);
        TreeNode t3 = new TreeNode(3);
        TreeNode t4 = new TreeNode(4);
        TreeNode t5 = new TreeNode(5);
        TreeNode t6 = new TreeNode(6);
        TreeNode t7 = new TreeNode(7);
        TreeNode t8 = new TreeNode(8);
        t6.setLeft(t2);
        t6.setRight(t7);
        t2.setFather(t6);
        t7.setFather(t6);

        t2.setLeft(t1);
        t2.setRight(t5);
        t1.setFather(t2);
        t5.setFather(t2);

        t5.setLeft(t3);
        t3.setFather(t5);

        t3.setRight(t4);
        t4.setFather(t3);
        Solution solution = new Solution();
//        1 => 2 // 显然下一结点是 1 的父亲结点
        System.out.println(solution.findNext(t1));
//        2 => 3 // 下一节点是当前结点右孩子的左孩子结点，其实你也应该想到了，应该是一直到左孩子为空的那个结点
        System.out.println(solution.findNext(t2));
//        3 => 4 // 跟 2 的情况相似，当前结点右孩子结点的左孩子为空的那个结点
        System.out.println(solution.findNext(t3));
//        4 => 5 // 5 是父亲结点 3 的父亲结点，发现和1有点像，因为 1，3,同样是父亲结点的左孩子
        System.out.println(solution.findNext(t4));
//        5 => 6 // 跟 4=>5 一样的道理
        System.out.println(solution.findNext(t5));
//        6 => 7 // 跟 3=>4 一样的道理
        System.out.println(solution.findNext(t6));
//        7 => null // 因为属于最尾结点·k
        System.out.println(solution.findNext(t7));
    }
}
